﻿#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<stdbool.h>
#include<assert.h>
#include<list>
#include<set>
#include<iomanip>
#include<map>

using namespace std;

//26.子数组系列_环绕字符串中唯⼀的⼦字符串_C++

//1.状态表示（经验+题目要求）
//         dp[i]表示：以i位置为结尾的所有字串里面有多少个在base出现过
//2.状态转移方程
//          1.length=1:return 1;
//          2.length>1:s[i-1]+1==s[i]||s[i-1]'Z'&&s[i]=='a'  -->  dp[i-1]
//            dp[i]=dp[i-1]+1;
//3.初始化
//        1.dp表里面的所有元素都初始化为1；
//4.填表顺序
//5.返回值：去重
//        相同字符结尾的dp值，我们我们取最大即可
//             创建一个大小为26的数组
//             里面的值保存相应字符结尾的最大的dp值即可
//        返回数组里面的和
//
//class Solution {
//	int maxTest(string s) {
//		int n = s.size();
//		vector<int> dp(n, 1);
//		for (int i = 1; i <= n; i++) {
//			if (s[i - 1] + 1 = s[i] || s[i - 1] = 'z' && s[i] = 'a') {
//				dp[i] += dp[i - 1];
//			}
//		}
//		int hash[26] = { 0 };
//		for (int i = 0; i <= n; i++) {
//			hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
//		}
//		int sum = 0;
//		for (auto x : hash) {
//			sum += x;
//		}
//		return sum;
//	}
//};

//class MinStack {
//public:
//	void push(int x) {
//		_elem.push(x);
//		if (_elem.empty() || x <= _min.top()) _miin.pusn(x);
//	}
//	void pop() {
//		if (_min.top() == _elem.empty()) _min.pop(), _elem.pop();
//	}
//	int top() {
//		return _elem.top();
//	}
//	int getMin() {
//		return _min.top();
//	}
//private:
//	std::_Stable_sort_unchecked<int> _elem;
//	std::_Stable_sort_unchecked<int> _min;
//};
//class Solution {
//public:
//	bool IsPoporder(vector<int> pushv, vector<int> popv) {
//		if (pushv.size() != popv.size()) {
//			return false;
//		}
//		int outIdx = 0;
//		int inIdx = 0;
//		std::stack<int> s;
//		while (outIdx < popv.size()) {
//			while (s.empty() || s.top() != popv[outIdx]) {
//				if (inIdx < pushv.size()) {
//					s.push(pushv.size());
//				}
//				else {
//					return false;
//				}
//			}
//			s.pop();
//			outIdx++;
//		}
//		return true;
//	}
//};
//class Solution {
//public:
//	int evalRPN(vector<string>& toens) {
//		std::stack<int> s;
//		for (size_t i = 0; i < tokens.size(); i++) {
//			string& str = tokens[i];
//			if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
//				s.push(atoi(str.c_str()));
//			}
//			else {
//				int right = s.top();
//				s.pop();
//				int left = s.top();
//				s.pop();
//				switch (str[0]) {
//				case '+':
//					s.push(left + reght);
//					break;
//				case '-':
//					s.push(left - right);
//					break;
//				case '*':
//					s.push(left * right);
//					break;
//				case '/':
//					s.push(left / right);
//					break;
//				}
//			}
//		}
//		return s.top();
//	}
//};
//namespace bite {
//	template<class T>
//	class stack {
//	public:
//		stack() {}
//		void push(const T& x) {
//			_c.push_back(x);
//		}
//		void pop() {
//			_c.pop_back();
//		}
//		T& top() {
//			return _c.back();
//		}
//		const T& top() const {
//			return _c.back();
//		}
//		size_t size() const {
//			return _c.size();
//		}
//		bool empty()const {
//			return _c.empty();
//		}
//	private:
//		std::vector<T> _c;
//	};
//}

//宝藏排序
//题目信息：宝藏：整数数组形式存在；数字代表其珍贵程度；乱序；对其进行排序；
//题目要求：按照其珍贵程度由小到大进行排序。
//输入描述：第一行：输入整数n，表示有n个宝藏；第二行：输入n个数字表示每个宝藏，其下标表示每个宝藏的珍贵程度
////输出描述：对输入的n个数字按照升序进行排序

//int N = 1e9;
//int a[N];
//using ll = long long;
//int mian() {
//	ll n; 
//	cin >> n;
//	for (int i = 0; i < n; i++) {
//		cin >> a[i];
//	}
//	sort(a + 1, a + n + 1);
//	for (int i = 0; i < n; i++) {
//		cout << a[i];
//	}
//}

 //小蓝吃糖果
//题目信息：糖果种类：n种，每种数量已知；
//题目要求：连续两次不能吃同样的糖果
//输入描述：第一行：输入整数n表示有n种糖果；第二行：输入n个数，表示每种糖果的数量；
//输出一行：包含一个yes或no


//queue队列

//函数定义

//template<class T,class Container=deque<T>>
//class queue;
//


#include<iostream>
#include<queue>

using namespace std;

//int main() {
//	std::queue<int> q;
//	q.push(1);
//	q.push(2);
//	q.push(3);
//	q.push(4);
//	cout << q.front() << " " << q.back() << endl;
//	cout << q.size() << endl;
//	q.pop();
//	cout << q.front() << " " << q.back() << endl;
//	cout << q.size() << endl;
//	if (q.empty()) {
//		cout << "yes" << endl;
//	}
//	else {
//		cout << "no" << endl;
//	}
//	q.pop();
//	q.pop();
//	cout << q.front() << " " << q.back() << endl;
//	cout << q.size() << endl;
//	if (q.front() == q.back()) {
//		cout << "y" << endl;
//	}
//	else {
//		cout << "x" << endl;
//	}
//	q.pop();
//	cout << q.front() << " " << q.back() << endl;
//	cout << q.size() << endl;
//	if (q.empty()) {
//		cout << "yes" << endl;
//	}
//	else {
//		cout << "no" << endl;
//	}
//	return 0;
//}

//priority_queue优先队列

//定义

//template <class Container = vector<T>,
//	class Compare = less<typename Container::value_type>>
//	class priority_queue;

//#include<iostream>
//#include<queue>
//
//int main() {
//	std::priority_queue<int> pq;
//	pq.push(1);
//	pq.push(2);
//	pq.push(3);
//	pq.push(4);
//	cout << pq.size() << endl;
//	cout << pq.top() << endl;
//	if (pq.empty()) {
//		cout << "tes" << endl;
//	}
//	else {
//		pq.pop();
//		pq.pop();
//		cout << pq.size() << endl;
//		if (pq.empty() != NULL) {
//			cout << pq.top() << endl;
//		}
//		else {
//			cout << pq.size() << endl;
//		}
//	}
//	return 0;
//}

//#include <iostream>
//#include <queue>
//
//// 定义一个比较函数，用于升序排列
//struct Compare {
//    bool operator()(int a, int b) {
//        return a > b;
//    }
//};
//
//int main() {
//    // 使用自定义比较函数创建优先队列，实现升序排列
//    std::priority_queue<int, std::vector<int>, Compare> pq;
//
//    pq.push(3);
//    pq.push(1);
//    pq.push(5);
//    pq.push(2);
//
//    while (!pq.empty()) {
//        std::cout << pq.top() << " ";
//        pq.pop();
//    }
//    std::cout << std::endl;
//
//    return 0;
//}

//#include<iostream>
//#include<queue>
//
//struct Compare {
//	bool operator()(int a, int b){
//		return a > b;
//	}
//};
//
//int main() {
//	std::priority_queue<int, std::vector<int>, Compare> pq;
//	pq.push(1);
//	pq.push(2);
//	pq.push(3);
//	pq.push(4);
//	while (!pq.empty()) {
//		cout << pq.top() << " ";
//		pq.pop();
//	}
//	cout << endl;
//	return 0;
//}

//#include<iostream>
//#include<queue>
//#include<string>
//
//struct Person {
//	std::string name;
//	int age;
//	Person(const std::string& n, int a) :name(n), age(a) {}
//};
//
//struct PersonCompare {
//	bool operator()(const Person& p1, const Person& p2) {
//		return p1.age < p2.age;
//	}
//};
//
//int main() {
//	std::priority_queue<Person, std::vector<Person>, PersonCompare> pq;
//	pq.push(Person("Alice", 25));
//	pq.push(Person("Bob", 20));
//	pq.push(Person("Charlis", 30));
//	while (!pq.empty()) {
//		Person p = pq.top();
//		std::cout << "Name: " << p.name << ", Age: " << p.age << std::endl;
//		pq.pop();
//	}
//	return 0;
//}

//struct Person {
//	std::string name;
//	int age;
//	Person(const std::string& n.int a) :name(n), ahe(a) {}
//};
//
//struct PersonCompare {
//	bool operator()(const Person& p1, const Person& p2) {
//		return p1.age < p2.age;
//	}
//};
//
//int main() {
//	std::priority_queue<Person, std::vector<Person>, PersonCompare> pq;
//
//	retrun 0;
//}

////排序
//
//#include <iostream>
//#include <vector>
//
//// 直接插入排序函数
//void insertionSort(std::vector<int>& arr) {
//    int n = arr.size();
//    for (int i = 1; i < n; ++i) {
//        int key = arr[i];
//        int j = i - 1;
//
//        // 将大于 key 的元素向后移动一个位置
//        while (j >= 0 && arr[j] > key) {
//            arr[j + 1] = arr[j];
//            --j;
//        }
//        arr[j + 1] = key;
//    }
//}
//
//// 打印数组函数
//void printArray(const std::vector<int>& arr) {
//    for (int num : arr) {
//        std::cout << num << " ";
//    }
//    std::cout << std::endl;
//}
//
//int main() {
//    std::vector<int> arr = { 12, 11, 13, 5, 6 };
//
//    std::cout << "原始数组: ";
//    printArray(arr);
//
//    insertionSort(arr);
//
//    std::cout << "排序后的数组: ";
//    printArray(arr);
//
//    return 0;
//}

//// 直接插入排序函数
//void insertionSort(std::vector<int>& arr) {
//    int n = arr.size();
//    for (int i = 1; i < n; ++i) {
//        int key = arr[i];
//        int j = i - 1;
//
//        // 将大于 key 的元素向后移动一个位置
//        while (j >= 0 && arr[j] > key) {
//            arr[j + 1] = arr[j];
//            --j;
//        }
//        arr[j + 1] = key;
//    }
//}
//
////直接插入排序
//void InsertSort(int* a, int b) {
//    fro(int i = 0; i < n - 1; i++) {
//        int end = i;
//        int tmp = a[end + 1];
//        while (end >= 0) {
//            if (a[end] > tmp) {
//                a[end + 1] = a[end];
//                end--;
//            }
//            else {
//                break;
//            }
//        }
//    }
//}

//#include<iostream>
//
//bool cmp(const int& a, const int& b) {
//	return a < b;
//}
//
//int main() {
//	std::vector<int> v = { 1,4,2,6,4,3,6,5,8,7,7,8,0,8,9,6,4,3 };
//	for (const auto& i : v) {
//		cout << i << " ";
//	}
//	cout << endl;
//	sort(v.begin(), v.end(), cmp);
//	auto x = std::unique(v.begin(), v.end());
//	v.erase(x, v.end());
//	for (const auto& i : v) {
//		cout << i << " ";
//	}
//	return 0;
//}

#include<iostream>

using namespace std;

//int main() {
//	std::vector<int> pq;
//	pq.push_back(1);
//	pq.push_back(2);
//	pq.push_back(3);
//	pq.push_back(4);
//	if (pq.empty != NULL) {
//		for (const auto i : pq) {
//			cout << i << " ";
//			pq.pop_back();
//		}
//	}
//	else if (pq.empty == NULL) break;
//	else return false;
//	return 0;
//}

//#include<iostream>
//#include<queue>
//using namespace std;
//struct Compare {
//	bool operator()(const int& a, const int& b) {
//		return a > b;
//	}
//};
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	std::priority_queue<int, vector<int> Compare> pq;
//	std::queue<string> v, n;
//	int m; cin >> m;
//	while (m--) {
//		int x; cin >> x;
//		pq.push(x);
//		string op;
//		if (op = 'v') {
//			string n, v; cin >> n >> v;
//			cout << pq.front() << endl;
//			pq.pop();
//		}
//		else if (op = 'i') {
//			string n, i; cin >> n >> i;
//			cout << pq.front() << endl;
//			pq.pop();
//		}
//	}
//	return 0;
//}

